The Mage Winds is a series of three novels called Winds of Fate, Winds of Change, and Winds of Fury in that order. They are by Mercedes Lackey.
The trilogy is about a woman named Elspeth and a man named Darkwind. In most of the first book it is alternating between the characters' lives, and Elspeth is getting ready to go on a journey to become a mage, and be the first of the new Herald-Mages. Darkwind is living his routine life in the k'Sheyna vale not wanting to ever see magic again after the death of his mother when the magic was being moved from one heartstone to the other. As the tale goes on Elspeth, in search of a teacher to teach her magery, she soon ends up very near Darkwind and meets him.